package com.ocean.greedy.easy;

import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class LongestPalindrome {

    public static void main(String[] args) {
        String s = "abccccdd";
        s = "a";
        s = "aaaaaccc";
        LongestPalindrome palindrome = new LongestPalindrome();
        int res = palindrome.longestPalindrome3(s);
        System.out.println(res);
    }

    public int longestPalindrome3(String s) {
        if (s.length() == 1) {
            return 1;
        }
        int[] nums = new int[128];
        int m = s.length();
        int ans = 0;
        for (int i = 0; i < m; i++) {
            char c = s.charAt(i);
            // 改字母作为下标 数量作为值
            nums[c]++;
        }
        for (int count : nums) {
            ans += count / 2 * 2;
            if (count % 2 == 1 && ans % 2 == 0) {
                ans++;
            }
        }
        return ans;
    }


    public int longestPalindrome(String s) {
        if (s.length() == 1) {
            return 1;
        }
        Map<Character, Integer> map = new HashMap<>();
        int n = s.length();
        int paired = 0;
        int noPaired = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
            if (map.get(c) % 2 == 1) {
                // 说明不成对
                noPaired++;
            } else {
                // 成对
                paired++;
                noPaired--;
            }
        }
        noPaired = noPaired >= 1 ? 1 : 0;
        return 2 * paired + noPaired;
    }


    public int longestPalindrome2(String s) {
        if (s.length() == 1) {
            return 1;
        }
        Map<Character, Integer> map = new HashMap<>();
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);

        }
        Set<Map.Entry<Character, Integer>> entries = map.entrySet();
        int res = 0;
        int paired = 0;
        Collection<Integer> values = map.values();
        for (Integer value : values) {
            if (value % 2 == 1) {
                // 说明这个元素不成对
                paired++;
                if (value - 1 > 0) {
                    res += value - 1;
                }
            } else {
                res += value;
            }
        }
        paired = paired >= 1 ? 1 : 0;
        return res + paired;
    }


}
